home *** CD-ROM | disk | FTP | other *** search
/ HyperLib 1997 Winter - Disc 1 / HYPERLIB-1997-Winter-CD1.ISO.7z / HYPERLIB-1997-Winter-CD1.ISO / オンラインウェア / UTIL / Natural Order.sit / Natural Order / Sources / Natural Order.c next >
C/C++ Source or Header  |  1996-11-04  |  9KB  |  231 lines
  1. // Natural Order
  2. // ｩ1996 Stuart Cheshire <cheshire@CS.Stanford.EDU>
  3. //
  4. // Natural Order patches IUMagString and IUMagPString to make them sort strings containing
  5. // numbers in a sensible order
  6. // See Natural Order ReadMe for more details
  7. // See TextUtils.h for the declaration of IUMagString, IUMagPString etc.
  8.  
  9. #include <Traps.h>
  10. #include "StuTypes.h"
  11.  
  12. // If USE_SYS_PACK6 is set to 1, the patch calls through to the underlying system sorting routine
  13. // to sort the textual parts of the strings. This preserves language-specific sorting orders.
  14. // If USE_SYS_PACK6 is set to 0, the patch does entirely self-contained sorting, using only lexico-
  15. // graphic sorting of the textual parts of the strings based on the ASCII values of the characters.
  16.  
  17. #define USE_SYS_PACK6 1
  18.  
  19. #define isdigit(X) ((X) >= '0' && (X) <= '9')
  20.  
  21. void main(void);
  22. pascal short my_pack6(...);
  23. pascal short sys_pack6(const u_char *aPtr, const u_char *bPtr, short aLen, short bLen,
  24.                                                     Handle itl2Handle, short TrapSelector);
  25. #define SysMagPString(A,B,C,D,E) sys_pack6((A),(B),(C),(D),(E),0x001A)
  26.  
  27. local pascal short StuMagString(const u_char *aPtr, const u_char *bPtr, short aLen, short bLen,
  28.                                                     short TrapSelector);
  29. local pascal short StuMagPString(const u_char *aPtr, const u_char *bPtr, short aLen, short bLen,
  30.                                                     Handle itl2Handle, short TrapSelector);
  31.  
  32. // entry_point must be the first routine in the file
  33.  
  34. local void entry_point(void)    /* no stack frame please ! */
  35.     {
  36.     asm    {    
  37.     @0                    move.l    a0, -(sp)
  38.                         DetachResource
  39.                         bra        main
  40.  
  41.     extern my_pack6:    cmp.w    #0x000A, 4(sp)        ; IUMagString
  42.                         beq        StuMagString
  43.                         cmp.w    #0x001A, 4(sp)        ; IUMagPString
  44.                         beq        StuMagPString
  45.     extern sys_pack6:    jmp        0x12345678
  46.         }
  47.     }
  48.  
  49. #if USE_SYS_PACK6
  50.  
  51. // This version of StuMagPString calls through to the system's IUMagPString routine for
  52. // comparing the textual parts of strings.
  53. // See below for a self-contained version
  54.  
  55. // If string a sorts before b, return -1, else if b sorts before a, return 1, else return 0
  56. local pascal short StuMagPString
  57.     (const u_char *aPtr, const u_char *bPtr, short aLen, short bLen, Handle itl2Handle, short TrapSelector)
  58.     {
  59.     short result;
  60.     long zeroskip = 0;
  61.     const u_char *a = aPtr, *aEnd = a + aLen;
  62.     const u_char *b = bPtr, *bEnd = b + bLen;
  63.     
  64.     // While *either* string has any characters left, continue.
  65.     while (aPtr < aEnd || bPtr < bEnd)
  66.         {
  67.         // At first entry to the loop:
  68.         // a = aPtr = start of string a, and likewise b = bPtr = start of string b
  69.  
  70.         // On subsequent passes:
  71.         // Everything up to aPtr/bPtr has been compared already and found to be equal
  72.         // aPtr/bPtr point to the next characters to be compared (which may be digits)
  73.         // a/b point to the first non-digit characters in each string
  74.         
  75.         // Find end of non-digit characters in each string
  76.         // (i.e. no more characters left, or a character that's a digit)
  77.         while (a < aEnd && !isdigit(*a)) a++;
  78.         while (b < bEnd && !isdigit(*b)) b++;
  79.         
  80.         // Compare what we've got so far
  81.         // (possibly leading digits, possibly followed by non-digit characters)
  82.         result = SysMagPString(aPtr, bPtr, a-aPtr, b-bPtr, itl2Handle);
  83.  
  84.         // If they're unequal, we're finished
  85.         if (result) return (result);
  86.         
  87.         // If they're otherwise equal but we skipped a different number of zeroes
  88.         // in getting here, use that information to break the tie
  89.         if (zeroskip > 0) return(1); else if (zeroskip < 0) return(-1);
  90.         
  91.         // No, they're really completely equal, so we continue
  92.         
  93.         // Skip over leading zeroes on numbers (but not a single lone zero)
  94.         // We count the number of skipped zeroes in case we need it as a tie breaker later
  95.         while (a[0] == '0' && a < aEnd-1 && isdigit(a[1])) { a++; zeroskip++; }
  96.         while (b[0] == '0' && b < bEnd-1 && isdigit(b[1])) { b++; zeroskip--; }
  97.         
  98.         // Record where we're at (everything to here has been deemed 'equal')
  99.         aPtr = a;
  100.         bPtr = b;
  101.         
  102.         // Read all the digits, and see if one runs out first.
  103.         while (a < aEnd && isdigit(*a) && b < bEnd && isdigit(*b)) { a++; b++; }
  104.         // Now, at least one of a or b does not point to a digit
  105.  
  106.         // If string a has a digit left (and b doesn't) then, trivially, a is greater
  107.         if (a < aEnd && isdigit(*a)) return(1);
  108.         
  109.         // If string b has a digit left (and a doesn't) then, trivially, b is greater
  110.         if (b < bEnd && isdigit(*b)) return(-1);
  111.         
  112.         // Neither have digits left, so both have equal-length numbers, so go around the loop
  113.         // a second time and let SysMagPString be responsible for lexicographically comparing the
  114.         // numbers (lexicographic comparison works for numbers that are equal-length digit sequences).
  115.         }
  116.  
  117.     // Both strings ran out. That means they must be 'equal'
  118.     return(0);
  119.     }
  120.  
  121. #else
  122.  
  123. // This version of StuMagPString is completely self-contained. It does not call through
  124. // to the system's IUMagPString routine and it has no knowledge of language-specific
  125. // characteristics,such as how characters with accents should sort.
  126. // It should never normally be used as a patch for the system's IUMagPString routine, but the
  127. // code is included here simply as sample code for people who want to incorporate Natural Order's
  128. // sensible numeric sorting without the cost of calling the Mac's IU sorting routines.
  129. // See above for a version that respects the system's sorting order.
  130.  
  131. // If string a sorts before b, return -1, else if b sorts before a, return 1, else return 0
  132. local pascal short StuMagPString
  133.     (const u_char *aPtr, const u_char *bPtr, short aLen, short bLen, Handle itl2Handle, short TrapSelector)
  134.     {
  135.     short result;
  136.     long zeroskip = 0;
  137.     const u_char *a, *aEnd = aPtr + aLen;
  138.     const u_char *b, *bEnd = bPtr + bLen;
  139.     
  140.     // While *either* string has any characters left, continue.
  141.     while (aPtr < aEnd || bPtr < bEnd)
  142.         {
  143.         // Compare non-digit characters.
  144.         while (aPtr < aEnd && bPtr < bEnd)
  145.             {
  146.             u_char ac = *aPtr;
  147.             u_char bc = *bPtr;
  148.             if (isdigit(ac) && isdigit(bc)) break;    // If both are digits, break out
  149.             if (ac < bc) return(-1); else if (ac > bc) return(1);
  150.             aPtr++;
  151.             bPtr++;
  152.             }
  153.  
  154.         if (aPtr == aEnd && bPtr == bEnd) return(0);    // If both strings ran out, they're equal
  155.         if (aPtr == aEnd) return(-1);                    // If A ran out (and B didn't), A is less
  156.         if (bPtr == bEnd) return(1);                    // If B ran out (and A didn't), B is less
  157.  
  158.         // If they're otherwise equal but we skipped a different number of zeroes
  159.         // in getting here, use that information to break the tie
  160.         if (zeroskip > 0) return(1); else if (zeroskip < 0) return(-1);
  161.         
  162.         // No, they're really completely equal, so we continue
  163.         
  164.         // Skip over leading zeroes on numbers (but not a single lone zero)
  165.         // We count the number of skipped zeroes in case we need it as a tie breaker later
  166.         while (aPtr[0] == '0' && aPtr < aEnd-1 && isdigit(aPtr[1])) { aPtr++; zeroskip++; }
  167.         while (bPtr[0] == '0' && bPtr < bEnd-1 && isdigit(bPtr[1])) { bPtr++; zeroskip--; }
  168.  
  169.         // Record where we're at (everything to here has been deemed 'equal')
  170.         a = aPtr;
  171.         b = bPtr;
  172.  
  173.         // Read all the digits, and see if one runs out first.
  174.         while (a < aEnd && isdigit(*a) && b < bEnd && isdigit(*b)) { a++; b++; }
  175.         // Now, at least one of a or b does not point to a digit
  176.  
  177.         // If string a has a digit left (and b doesn't) then, trivially, a is greater
  178.         if (a < aEnd && isdigit(*a)) return(1);
  179.         
  180.         // If string b has a digit left (and a doesn't) then, trivially, b is greater
  181.         if (b < bEnd && isdigit(*b)) return(-1);
  182.         
  183.         // Neither have digits left, so both have equal-length numbers, so use
  184.         // lexicographical comparison decide which is greater (lexicographic
  185.         // comparison works for numbers that are equal-length digit sequences).
  186.         while (aPtr < a && bPtr < b)
  187.             {
  188.             if (*aPtr < *bPtr) return(-1); else if (*aPtr > *bPtr) return(1);
  189.             aPtr++;
  190.             bPtr++;
  191.             }
  192.         }
  193.  
  194.     // Both strings ran out. That means they must be 'equal'
  195.     return(0);
  196.     }
  197.  
  198. #endif
  199.  
  200. local pascal short StuMagString
  201.     (const u_char *aPtr, const u_char *bPtr, short aLen, short bLen, short TrapSelector)
  202.     {
  203.     return(StuMagPString(aPtr, bPtr, aLen, bLen, NULL, TrapSelector));
  204.     }
  205.  
  206. local Boolean TrapAvailable(u_long trap)
  207.     {
  208.     TrapType tType = (trap & 0x800 ? ToolTrap : OSTrap);
  209.     if (trap & 0x800)                // if it is a ToolBox Trap
  210.         {
  211.         u_long n = 0x400;    // number of toolbox traps
  212.         if (NGetTrapAddress(_InitGraf, ToolTrap) == NGetTrapAddress(0xAA6E, ToolTrap))
  213.             n = 0x200;
  214.         if ((trap &= 0x7FF) >= n) trap = _Unimplemented;
  215.         }
  216.     return(NGetTrapAddress(trap, tType) != NGetTrapAddress(_Unimplemented, ToolTrap));
  217.     }
  218.  
  219. typedef struct { WORD jmp; ProcPtr addr; } jmp;
  220. #define TBpatch(VEC,T,NEW) p=&((jmp*)VEC)->addr; ¥
  221.     *p = GetToolTrapAddress(T); SetToolTrapAddress((ProcPtr)NEW,T)
  222. #define OSpatch(VEC,T,NEW) p=&((jmp*)VEC)->addr; ¥
  223.     *p = GetOSTrapAddress(T); SetOSTrapAddress((ProcPtr)NEW,T)
  224.  
  225. export void main(void)
  226.     {
  227.     register ProcPtr *p;
  228.     TBpatch(sys_pack6, _Pack6, my_pack6);
  229.     if (TrapAvailable(_HWPriv)) FlushInstructionCache();
  230.     }
  231.